#include "initialise.h"

using namespace std;

//--------------------------------------------------------------------------------------
void fillGrid(int **grid, bool **fixed, int sqLen, int grLen, int nSq, int first, int last)
{
	//go through each square, and fill with appropriate numbers
	int r, c;
	for(r=0;r<nSq;r++){
		for(c=0;c<nSq;c++){
			fillSquare(r,c,grid,fixed,sqLen,first,last);
		}
	}
}

//--------------------------------------------------------------------------------------
void resetGrid(int **grid, bool **fixed, int grLen){
	int r,c;
	for(r=0;r<grLen;r++){
		for(c=0;c<grLen;c++){
			if(!fixed[r][c])grid[r][c]=-1;
		}
	}
}



//--------------------------------------------------------------------------------------
void fillSquare(int row, int col, int **grid, bool **fixed, int sqLen, int first, int last)
{
	int i,r,c,j,b,occCells=0;
	bool found;

	//identify how many cells per square
	int numCells = sqLen*sqLen;
	//make a list of the numbers that should go in each square
	int *list = new int [numCells];
	i=first;j=0;
	while(j<numCells){
		list[j]=i;
		i++;
		j++;
	}
	//Go through the square and identify which elements are already present
	//and tick them off the list (by making them -1)
	for(r=row*sqLen; r<(row+1)*sqLen;r++){
		for(c=col*sqLen; c<(col+1)*sqLen; c++){
			if(grid[r][c] != -1){
				//find grid[r][c] in list, and tick it off
				j=0; found = false;
				while(j<numCells && !found){
					if(list[j]==grid[r][c]){
						list[j]=-1;
						found =true;
					} 
					else j++;
				}
				occCells++;
			}
		}
	}
	int lenNewList = numCells-occCells;
	if (lenNewList > 0){
		int *newList = new int [lenNewList];
		i=0;j=0;
		while(i<numCells){
			if(list[i]!=-1){
				newList[j]=list[i];
				j++;
			}
			i++;
		}
		//randomly permute newList,
		for(i=lenNewList-1; i>1; i--){
			j = rand()%(i-1);
			b=newList[i]; newList[i]=newList[j]; newList[j]=b;
		}
		//.. and fill the square in
		j=0;
		for(r=row*sqLen; r<(row+1)*sqLen; r++){
			for(c=col*sqLen; c<(col+1)*sqLen; c++){
				if(grid[r][c]==-1){
					grid[r][c]=newList[j];
					j++;
				}
			}
		}
		delete [] list;
		delete [] newList;
	}
}

//--------------------------------------------------------------------------------------
bool gridOK(int **grid, int sqLen, int grLen, int first, bool **fixed)
{
	//First, we want to check that the grid is legal
	int r, c, j, count, r1, c1;
	bool valid = true;

	//Go through each row and check for duplicates
	for(r=0;r<grLen;r++){
		j=first;
		while(j<first+grLen){
			count=0;
			for(c=0;c<grLen;c++){
				if(grid[r][c]==j) count++;
			}
			if(count>1){
				cout<<"Error. There are "<<count<<" occurences of "<<j<<" on row "<<r<<endl;
				valid = false;
			}
			j++;
		}
	}
	
	//Then columns
	for(c=0;c<grLen;c++){
		j=first;
		while(j<first+grLen){
			count=0;
			for(r=0;r<grLen;r++){
				if(grid[r][c]==j) count++;
			}
			if(count>1){
				cout<<"Error. There are "<<count<<" occurences of "<<j<<" in column "<<c<<endl;
				valid = false;
			}
			j++;
		}
	}

	//Then Squares
	for(r=0;r<sqLen;r++){
		for(c=0;c<sqLen;c++){
			j=first;
			while(j<first+grLen){
				count=0;
				//This goes through square r c
				for(r1=r*sqLen; r1<(r+1)*sqLen;r1++){
					for(c1=c*sqLen; c1<(c+1)*sqLen;c1++){
						if(grid[r1][c1]==j) count++;
					}
				}
				if(count>1){
					cout<<"Error. There are "<<count<<" occurences of "<<j<<" in square ["<<r<<","<<c<<"]\n";
					valid = false;
				}
				j++;
			}
		}
	}


	if(!valid) {
		cout<<"Grid is not valid"<<endl;
		return(valid);
	}
	else 
	{
		//The grid is valid, but we now want to to check to see if there are squares 
		//with just one entry missing in them
		for(r=0;r<sqLen;r++){
			for(c=0;c<sqLen;c++){
				count=0;
				//This goes through square r c
				for(r1=r*sqLen; r1<(r+1)*sqLen;r1++){
					for(c1=c*sqLen; c1<(c+1)*sqLen;c1++){
						if(grid[r1][c1]==-1) count++;
					}
				}
				if(count==1){
					//The nxn square contains just one unfixed cell. Complete the square with the appropriate value
					//and "fix" it.
					completeSquare(grid,r,c,sqLen,first,fixed);
				}
			}
		}
	}
	return(valid);
}


//--------------------------------------------------------------------------------------
void completeSquare(int **grid, int r, int c, int sqLen, int first, bool **fixed)
{
	int r1, c1, cellRow, cellCol, count=0;

	//Go through the square and check that, ideed, only one square is vacant
	for(r1=r*sqLen; r1<(r+1)*sqLen;r1++){
		for(c1=c*sqLen; c1<(c+1)*sqLen;c1++){
			if(grid[r1][c1]==-1) {
				cellRow = r1;
				cellCol = c1;
				count++;
			}
		}
	}
	if(count>1 || count<1){
		cout<<"Error. Should not be completing square ["<<r<<","<<c<<"]\n";
		exit(1);
	}
	else
	{
		//Need to identify which number is missig, stick it in the cell, and update
		//the fixed grid.
		int missingValue = -1;
		int j=first;
		bool found = false;
		while(j<first+(sqLen*sqLen) && !found)
		{
			bool jPresent=false;
			for(r1=r*sqLen; r1<(r+1)*sqLen;r1++){
				for(c1=c*sqLen; c1<(c+1)*sqLen;c1++){
					if(grid[r1][c1]==j){
						jPresent = true;
					}
				}
			}
			if(!jPresent){
				missingValue = j;
				found = true;
			}
			else j++;
		}
		grid[cellRow][cellCol]=missingValue;
		fixed[cellRow][cellCol]=true;
	}
}


